package com.leetcode.www;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。
 *
 * 返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。
 *
 * 两个下标i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shortest-distance-to-a-character
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-19
 * Time:10:49
 */
public class Everyday821 {
    public int[] shortestToChar(String s, char c) {//两次遍历
        int n = s.length();
        int[] ans = new int[n];

        for (int i = 0, idx = -n; i < n; ++i) {
            if (s.charAt(i) == c) {
                idx = i;
            }
            ans[i] = i - idx;
        }

        for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
            if (s.charAt(i) == c) {
                idx = i;
            }
            ans[i] = Math.min(ans[i], idx - i);
        }
        return ans;
    }
    public int[] shortestToChar1(String s, char c) {
        int[] nums = new int[s.length()];
        Arrays.fill(nums,Integer.MAX_VALUE);//填充全为最大值
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i < s.length();i ++){
            if(s.charAt(i) == c){
                list.add(i);//所有目标字符的下标
            }
        }
        for(int i = 0;i < s.length();i ++){
            for(int j = 0;j < list.size();j ++){
                int a = Math.abs(list.get(j) - i);//看距离大小
                nums[i] = Math.min(a,nums[i]);//取到最小值
            }
        }
        return nums;
    }
}
